package structure.mySort;

import java.util.Arrays;

public class OtherSort {

    /**
     * 计数排序:
     *  时间复杂度:O(N)
     *  空间复杂度:O(M) M:代表 当前数据的范围 (例如:900~999)
     *  一般适用于 有n个数,数据范围是 0~n 之间的
     * @param array 待排序数组
     */
    public static void countingSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] < minVal){
                minVal = array[i];
            }
            if (array[i] > maxVal){
                maxVal = array[i];
            }
        }
        //说明,已经找到了最大值和最小值.
        int[] count = new int[maxVal-minVal+1];
        //统计array数组当中,每个数据出现的次数
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            //为了空间合理使用,需要 index-minVal (例:923-900)
            count[index-minVal]++;
        }
        //说明,在计数数组当中,已经把array数组当中,每个数据出现的次数已经统计好了
        //接下来,只需要,遍历计数数组,把数据写回array
        int indexArray = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0){
                //这里一定要加minVal,因为不一定就是i出现了count[i]
                array[indexArray] = minVal + i;
                indexArray++;//下标向后移动
                count[i]--;//拷贝一个后,次数也就减少一次
            }
        }

    }

    public static void main(String[] args) {
        int[] array = {5,12,9,23,4,10,1};
        countingSort(array);
        System.out.println(Arrays.toString(array));
    }
}
